from structure.node import Node


class UnorderedList:
    def __init__(self):
        self.head = None

    def add(self, item):
        tmp = Node(item)
        tmp.next = self.head
        self.head = tmp

    def remove(self, item):
        cur = self.head
        prev = None
        while cur != None and cur.data != item:
            prev = cur
            cur = cur.next

        if cur.data == None:
            head = None
        else:
            prev.next = cur.next

    def search(self, item):
        cur = self.head
        while cur != None and cur.data != item:
            cur = cur.next
        if cur == None:
            return False
        else:
            return True

    def isEmpty(self):
        return self.head == None

    def size(self):
        count = 0
        cur = self.head
        while cur is not None and cur.next is not None:
            cur = cur.next
            count += 1

        if cur is not None:
            count += 1

        return count

    def append(self, item):
        cur = self.head
        while cur != None and cur.next != None:
            cur = cur.next
        cur.next = item

    def index(self, item):
        count = 0
        cur = self.head
        while cur is not None and cur.data != item:
            cur = cur.next
            count += 1
        return count

    def insert(self, pos, item):
        tmp = Node(item)
        count = 0
        cur = self.head
        prev = None
        while count < pos:
            prev = cur
            cur = cur.next
            count += 1
        prev.next = tmp
        tmp.next = cur


    def pop(self, pos=0):
        cur = self.head
        prev = None
        count = 0
        if self.head is None:
            return 'Empty list'
        else:
            while cur.next is not None and count<pos:
                prev = cur
                cur = cur.next
                count += 1
            if count<pos:
                return 'position is out of list boundary'
            elif prev is None:
                self.head = None
                return cur.data
            else:
                prev.next = cur.next
                return cur.data

    def __str__(self):
        cur = self.head
        s = ''
        while cur is not None:
            s = s + ', ' + cur.data
            cur = cur.next
        return s


class OrderedList:
    def __init__(self):
        self.head = None

    def add(self, item):
        tmp = Node(item)
        prev = None
        cur = self.head
        while cur != None and cur.data < item:
            prev = cur
            cur = cur.next
        prev.next = tmp
        tmp.next = cur

    def remove(self, item):
        cur = self.head
        prev = None
        while cur != None and cur.data != item:
            prev = cur
            cur = cur.next

        if cur.data == None:
            head = None
        else:
            prev.next = cur.next

    def search(self, item):
        cur = self.head
        while cur != None and cur.data < item:
            cur = cur.next
        if cur.data == item:
            return True
        else:
            return False

    def isEmpty(self):
        return self.head == None

    def size(self):
        count = 0
        cur = self.head
        while cur is not None and cur.next is not None:
            cur = cur.next
            count += 1

        return count

    def index(self, item):
        count = 0
        cur = self.head
        while cur != None and cur.data < item:
            cur = cur.next
            count += 1
        return count


    def pop(self, pos):
        cur = self.head
        prev = None
        count = 0
        if self.head is None:
            return 'Empty list'
        else:
            while cur.next is not None and count < pos:
                prev = cur
                cur = cur.next
                count += 1
            if count < pos:
                return 'position is out of list boundary'
            elif prev is None:
                self.head = None
                return cur.data
            else:
                prev.next = cur.next
                return cur.data
